package dfs;
import java.util.ArrayList;
import java.util.List;

//找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
public class 组合总和3 {
    List<List<Integer>> lists = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> list = new ArrayList<>();
        dfs(k,n,list,1);
        return lists;
    }

    private void dfs(int k, int n, List<Integer> list,int start) {
        if (list.size()==k && n==0)
            lists.add(new ArrayList<>(list));
        for (int i = start; i <10 ; i++) {
            if (i>n)
                continue;
            list.add(i);
            dfs(k,n-i,list,i+1);
            list.remove(list.size()-1);
        }
    }
}
